package backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 491. 非递减子序列
 * User: Li_yizYa
 * Date: 2025/6/19
 * Time: 20:15
 */
public class Solution10 {
    public static List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ret;
        }
        List<Integer> tmp = new ArrayList<>();
        backTracking(nums, ret, tmp, 0);
        return ret;
    }
    private static void backTracking(int[] nums, List<List<Integer>> ret, List<Integer> tmp, int index) {
        if (tmp.size() > 1) {
            ret.add(new ArrayList<>(tmp));
        }
        int[] used = new int[201]; // 每一个 used 数组只在当前层生效
        for (int i = index ; i < nums.length; i++) {
            if (!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1) || used[nums[i] + 100] == 1) {
                continue;
            }
            used[nums[i] + 100] = 1;
            tmp.add(nums[i]);
            backTracking(nums, ret, tmp, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 6, 7, 7};
        List<List<Integer>> ret = findSubsequences(nums);
        for (int i = 0; i < ret.size(); i++) {
            List<Integer> tmp = ret.get(i);
            for (int j = 0; j < tmp.size(); j++) {
                System.out.print(tmp.get(j) + " ");
            }
            System.out.println();
        }
    }
}
